def levenshtein_distance(a, b):
    m = [ [0] * (len(b) + 1) for i in range(len(a) + 1) ]

    for i in xrange(len(a) + 1):
        m[i][0] = i

    for j in xrange(len(b) + 1):
        m[0][j] = j

    for i in xrange(1, len(a) + 1):
        for j in xrange(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                x = 0
            else:
                x = 1
            m[i][j] = min(m[i - 1][j] + 1, m[i][ j - 1] + 1, m[i - 1][j - 1] + x)
    # print m
    return m[-1][-1]

def levenshtein_mapping(a,b):
    """
    author: funaya@gmail.com, hiroyuki-fn in Twitter
    
    input: two lists: lista and list b
    output: mapping of which elements in a corresponds to which elements in b
            in terms of Levenshtein distance
    
    """
    m = [ [0] * (len(b) + 1) for i in range(len(a) + 1) ]

    for i in xrange(len(a) + 1):
        m[i][0] = i

    for j in xrange(len(b) + 1):
        m[0][j] = j

    for i in xrange(1, len(a) + 1):
        for j in xrange(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                x = 0
            else:
                x = 1
            m[i][j] = min(m[i - 1][j] + 1, m[i][ j - 1] + 1, m[i - 1][j - 1] + x)
            
    # calculating mapping
    lmap = []
    i = len(a)
    j = len(b)
    
    while i >= 1 and j >= 1:
        candidates = [m[i - 1][j - 1], m[i - 1][j] , m[i][j - 1] ]
        next_distance = min(candidates)
        cani = [[i - 1, j - 1], [i - 1 , j], [i , j - 1]]
        
        if ( m[i][j] == next_distance ) and ( candidates.index(next_distance) == 0) :
            lmap.append([i-1, j-1])
            
        i, j = cani[candidates.index(next_distance)]
           
    lmap.reverse() 
    return lmap
    
    

a = ["You", "are", "insane"]
b = ["You", "truly" ,"are", "insane"]
map = levenshtein_mapping(a, b)

for m in map:
    print a[m[0]], b[m[1]]